package com.hy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:网格图中最少访问的格子数
 * <p>
 * 给你一个下标从 0 开始的 m x n 整数矩阵 grid 。你一开始的位置在 左上角 格子 (0, 0) 。
 * 当你在格子 (i, j) 的时候，你可以移动到以下格子之一：
 * 满足 j < k <= grid[i][j] + j 的格子 (i, k) （向右移动），或者
 * 满足 i < k <= grid[i][j] + i 的格子 (k, j) （向下移动）。
 * 请你返回到达 右下角 格子 (m - 1, n - 1) 需要经过的最少移动格子数，如果无法到达右下角格子，请你返回 -1 。
 *
 * User:Mr.Du
 * Date:2024/3/22
 * Time:17:06
 */
public class MinimumVisitedCells {

    /**
     * 垃圾做法，超时
     * @param grid
     * @return
     */
    public int minimumVisitedCells(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];

        for(int i = 0;i < m;i++){
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[0][0] = 1;
        // 计算第一列的最小步数
        for(int i = 1; i < m; i++) {
            for(int j = 0; j < i; j++) {
                if(dp[j][0] != Integer.MAX_VALUE && i <= grid[j][0] + j) {
                    dp[i][0] = Math.min(dp[i][0], dp[j][0] + 1);
                }
            }
        }

        // 计算第一行的最小步数
        for(int i = 1; i < n; i++) {
            for(int j = 0; j < i; j++) {
                if(dp[0][j] != Integer.MAX_VALUE && i <= grid[0][j] + j) {
                    dp[0][i] = Math.min(dp[0][i], dp[0][j] + 1);
                }
            }
        }

        // 计算其他位置的最小步数
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                for(int k = 0; k < j; k++) {
                    if(dp[i][k] != Integer.MAX_VALUE && j <= grid[i][k] + k) {
                        dp[i][j] = Math.min(dp[i][j], dp[i][k] + 1);
                    }
                }
                for(int k = 0; k < i; k++) {
                    if(dp[k][j] != Integer.MAX_VALUE && i <= grid[k][j] + k) {
                        dp[i][j] = Math.min(dp[i][j], dp[k][j] + 1);
                    }
                }
            }
        }
        return dp[m-1][n-1] == Integer.MAX_VALUE? -1 : dp[m-1][n-1];
    }

    public int minimumVisitedCells1(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int mn = 0;
        List<int[]>[] colStacks = new ArrayList[n]; // 每列的单调栈，为了能二分用 ArrayList
        Arrays.setAll(colStacks, i -> new ArrayList<int[]>());
        List<int[]> rowSt = new ArrayList<>(); // 行单调栈
        for (int i = m - 1; i >= 0; i--) {
            rowSt.clear();
            for (int j = n - 1; j >= 0; j--) {
                int g = grid[i][j];
                List<int[]> colSt = colStacks[j];
                mn = i < m - 1 || j < n - 1 ? Integer.MAX_VALUE : 1;
                if (g > 0) { // 可以向右/向下跳
                    // 在单调栈上二分查找最优转移来源
                    int k = search(rowSt, j + g);
                    if (k < rowSt.size()) {
                        mn = rowSt.get(k)[0] + 1;
                    }
                    k = search(colSt, i + g);
                    if (k < colSt.size()) {
                        mn = Math.min(mn, colSt.get(k)[0] + 1);
                    }
                }
                if (mn < Integer.MAX_VALUE) {
                    // 插入单调栈
                    while (!rowSt.isEmpty() && mn <= rowSt.get(rowSt.size() - 1)[0]) {
                        rowSt.remove(rowSt.size() - 1);
                    }
                    rowSt.add(new int[]{mn, j});
                    while (!colSt.isEmpty() && mn <= colSt.get(colSt.size() - 1)[0]) {
                        colSt.remove(colSt.size() - 1);
                    }
                    colSt.add(new int[]{mn, i});
                }
            }
        }
        return mn < Integer.MAX_VALUE ? mn : -1; // 最后一个算出的 mn 就是 f[0][0]
    }

    // 开区间二分
    private int search(List<int[]> st, int target) {
        int left = -1, right = st.size(); // 开区间 (left, right)
        while (left + 1 < right) { // 区间不为空
            int mid = left + (right - left) / 2;
            if (st.get(mid)[1] <= target) {
                right = mid; // 范围缩小到 (left, mid)
            } else {
                left = mid; // 范围缩小到 (mid, right)
            }
        }
        return right;
    }
}
